//
// The Epoch Language Project
// EPOCHCOMPILER Compiler Toolchain
//
// Traversal logic for handling the Abstract Syntax Tree
//
// The parser layer generates an AST, which consists of a series of
// nodes representing the parsed program. The AST contains only a
// minimal amount of semantic information; it is the responsibility
// of the Intermediate Representation layers to add semantic markup
// to the tree and generate different data structures that can be
// used by various phases of the compiler.
//
// We separate the logic of traversing the AST from the actual code
// that operates on the AST. This decoupling allows multiple different
// operations to be performed on the AST, without redundant traversal
// logic, and without necessitating the pollution of multiple operations
// crammed into a single code path.
//
// This decoupling is accomplished using functors which are invoked
// on the entry into each AST node, and the exit from that node. The
// tree is traversed depth-first with preorder semantics. This enables
// the callback code to change its state based on its location in the
// AST, and thereby interpret different node types in various contexts.
// This is especially useful for generic nodes like "identifiers" which
// may appear in many different contexts.
//

#pragma once


// Dependencies
#include "Compiler/Abstract Syntax Tree/Program.h"
#include "Compiler/Abstract Syntax Tree/CodeBlock.h"
#include "Compiler/Abstract Syntax Tree/AnyStatement.h"
#include "Compiler/Abstract Syntax Tree/Identifiers.h"

#include "Compiler/Abstract Syntax Tree/Assignment.h"
#include "Compiler/Abstract Syntax Tree/Entities.h"
#include "Compiler/Abstract Syntax Tree/Function.h"
#include "Compiler/Abstract Syntax Tree/Statement.h"
#include "Compiler/Abstract Syntax Tree/Structures.h"
#include "Compiler/Abstract Syntax Tree/Expression.h"
#include "Compiler/Abstract Syntax Tree/TypeDefinitions.h"


namespace ASTTraverse
{
    struct Traverser;


	//
	// Internal implementation details
	//
	namespace
	{
		//
		// SFINAE helper for determining if a given type fits the interface
		// of a boost variant. This is admittedly a very kludgy kind of thing
		// to do, but it's split into a separate template metaprogramming
		// helper so that we can improve on it later with minimal effects on
		// the code that relies on this concept.
		//
		// A complete treatment of how this technique works can be found here:
		// http://code.google.com/p/scribblings-by-apoch/wiki/MetaProgrammingEnableIfConvertible
		//
		// Instead of detecting a conversion between types, however, this code
		// detects the presence of a typedef named "types" in the target class.
		//
		template <typename T>
		struct IsVariantType
		{
			typedef char (&yes)[1];
			typedef char (&no)[2];

			template <typename U>
			static yes TestDummy(typename U::types*);

			template <typename U>
			static no TestDummy(...);

			enum PerformCheck
			{
				value = (sizeof(TestDummy<T>(NULL)) == sizeof(yes))
			};
		};

    }

	//
	// Special dummy markers used for indicating to the callback
	// wrapper code what kind of AST nodes to expect. These are
	// useful for differentiating between similar branches of the
	// AST that can't necessarily be recognized just by looking
	// at the nodes themselves. This enables context-sensitive
	// handling of the AST branches based on more than just the
	// node types themselves.
	//
	namespace Markers
	{
		struct FunctionReturnExpression { };
		struct ExpressionComponentPrefixes { };
		struct FunctionSignatureParams { };
		struct FunctionSignatureReturn { };
		struct StructureFunctionParams { };
		struct StructureFunctionReturn { };
		struct TemplateArgs { };
	}

	//
	// The actual AST traveral logic
	//
	// This struct completely encapsulates the process of walking
	// through the AST as generated by the parser layer. By using
	// this approach we protect AST examination/manipulation code
	// from the gory details of how the AST is really structured.
	//
	// We also insulate the traversal itself from the details of
	// what various operations on the AST actually want to do.
	//
	struct Traverser
	{
		//
		// Traverse a node of otherwise unknown type
		//
		// Generally used only for leaf nodes in the AST. Nodes that
		// have children should receive their own overloads so that
		// those child nodes can be traversed correctly. Traversal of
		// child nodes should never be left to the callback functors.
		//
		template <typename EntryActionT, typename ExitActionT, typename NodeT>
		void Do(EntryActionT& entryaction, NodeT& node, ExitActionT& exitaction)
		{
            DoerDispatcher<NodeT, IsVariantType<NodeT>::value>::Do(this, entryaction, node, exitaction);
		}

		//
		// Traverse a deferred-construction node
		//
		// Unwraps the node content from the deferred-construction
		// wrapper and traverses the content using the appropriate
		// overload of Do(). See the notes on the Deferred<> class
		// for more details.
		//
		template <typename EntryActionT, typename ExitActionT, typename T, typename PtrT>
		void Do(EntryActionT& entryaction, AST::Deferred<T, PtrT>& deferred, ExitActionT& exitaction)
		{
			Do(entryaction, *deferred.Content, exitaction);
		}

		//
		// Traverse a deferred-construction container
		//
		// Like deferred-construction nodes, containers are simply
		// wrapped to minimize copies and dynamic allocation while
		// parsing. This overload unwraps the container and passes
		// it off to the appropriate Do() overload.
		//
		template <typename EntryActionT, typename ExitActionT, typename T, typename PtrT>
		void Do(EntryActionT& entryaction, AST::DeferredContainer<T, PtrT>& deferred, ExitActionT& exitaction)
		{
			Do(entryaction, deferred.Content->Container, exitaction);
		}

		//
		// Traverse a container of nodes
		//
		// Often, AST nodes are held in a container to represent a
		// many-to-one child/parent relationship in the tree. This
		// overload recursively traverses each child node in turn,
		// providing depth-first pre-order traversal semantics.
		//
		template <typename EntryActionT, typename ExitActionT, typename T, typename AllocT>
		void Do(EntryActionT& entryaction, std::vector<T, AllocT>& nodes, ExitActionT& exitaction)
		{
			for(typename std::vector<T, AllocT>::iterator iter = nodes.begin(); iter != nodes.end(); ++iter)
				Do(entryaction, *iter, exitaction);
		}

		//
		// Traverse a base type in a sum type definition
		//
		template <typename EntryActionT, typename ExitActionT>
		void Do(EntryActionT& entryaction, AST::SumTypeBaseType& sumbase, ExitActionT& exitaction)
		{
			entryaction(sumbase.TypeName);
			exitaction(sumbase.TypeName);

			Do(entryaction, sumbase.TemplateArgs, exitaction);
		}

		//
		// Traverse a sum type definition
		//
		template <typename EntryActionT, typename ExitActionT>
		void Do(EntryActionT& entryaction, AST::SumType& sumtype, ExitActionT& exitaction)
		{
			entryaction(sumtype);
			Do(entryaction, sumtype.TemplateParams, exitaction);
			Do(entryaction, sumtype.AdditionalBaseTypes, exitaction);
			exitaction(sumtype);
		}

		//
		// Traverse an Epoch statement
		//
		template <typename EntryActionT, typename ExitActionT>
		void Do(EntryActionT& entryaction, AST::Statement& statement, ExitActionT& exitaction)
		{
			entryaction(statement);

			Markers::TemplateArgs marker;
			entryaction(marker);
			Do(entryaction, statement.TemplateArgs, exitaction);
			exitaction(marker);

			Do(entryaction, statement.Params, exitaction);
			exitaction(statement);
		}

		//
		// Traverse an Epoch expression
		//
		template <typename EntryActionT, typename ExitActionT>
		void Do(EntryActionT& entryaction, AST::Expression& expression, ExitActionT& exitaction)
		{
			entryaction(expression);
			Do(entryaction, expression.First, exitaction);
			Do(entryaction, expression.Remaining, exitaction);
			exitaction(expression);
		}

		//
		// Traverse a component of an Epoch expression
		//
		template <typename EntryActionT, typename ExitActionT>
		void Do(EntryActionT& entryaction, AST::ExpressionComponent& component, ExitActionT& exitaction)
		{
			entryaction(component);
			Markers::ExpressionComponentPrefixes prefixes = Markers::ExpressionComponentPrefixes();
			entryaction(prefixes);
			Do(entryaction, component.UnaryPrefixes, exitaction);
			prefixes = Markers::ExpressionComponentPrefixes();
			exitaction(prefixes);
			Do(entryaction, component.Component.Content->V, exitaction);
			exitaction(component);
		}

		//
		// Traverse a fragment of an Epoch expression
		//
		template <typename EntryActionT, typename ExitActionT>
		void Do(EntryActionT& entryaction, AST::ExpressionFragment& fragment, ExitActionT& exitaction)
		{
			entryaction(fragment);
			Do(entryaction, fragment.Component.Content->Component.Content->V, exitaction);
			exitaction(fragment);
		}

		//
		// Traverse an Epoch assignment
		//
		template <typename EntryActionT, typename ExitActionT>
		void Do(EntryActionT& entryaction, AST::Assignment& assignment, ExitActionT& exitaction)
		{
			entryaction(assignment);
			Do(entryaction, assignment.RHS, exitaction);
			exitaction(assignment);
		}

		//
		// Traverse a simple-LHS Epoch assignment
		//
		template <typename EntryActionT, typename ExitActionT>
		void Do(EntryActionT& entryaction, AST::SimpleAssignment& assignment, ExitActionT& exitaction)
		{
			entryaction(assignment);
			Do(entryaction, assignment.RHS, exitaction);
			exitaction(assignment);
		}

		//
		// Traverse a variable initialization
		//
		template <typename EntryActionT, typename ExitActionT>
		void Do(EntryActionT& entryaction, AST::Initialization& initialization, ExitActionT& exitaction)
		{
			entryaction(initialization);
			
			Markers::TemplateArgs marker;
			entryaction(marker);
			Do(entryaction, initialization.TemplateArgs, exitaction);
			exitaction(marker);

			Do(entryaction, initialization.RHS, exitaction);
			exitaction(initialization);
		}

		//
		// Traverse a block of code
		//
		template <typename EntryActionT, typename ExitActionT>
		void Do(EntryActionT& entryaction, AST::CodeBlock& codeblock, ExitActionT& exitaction)
		{
			entryaction(codeblock);
			Do(entryaction, codeblock.Entries, exitaction);
			exitaction(codeblock);
		}

		//
		// Traverse an entity invocation, including any chained entities
		//
		template <typename EntryActionT, typename ExitActionT>
		void Do(EntryActionT& entryaction, AST::Entity& entity, ExitActionT& exitaction)
		{
			entryaction(entity);
			Do(entryaction, entity.Parameters, exitaction);
			Do(entryaction, entity.Code, exitaction);
			Do(entryaction, entity.Chain, exitaction);
			exitaction(entity);
		}

		//
		// Traverse a postfix entity invocation
		//
		template <typename EntryActionT, typename ExitActionT>
		void Do(EntryActionT& entryaction, AST::PostfixEntity& entity, ExitActionT& exitaction)
		{
			entryaction(entity);
			Do(entryaction, entity.Parameters, exitaction);
			Do(entryaction, entity.Code, exitaction);
			Do(entryaction, entity.PostfixIdentifier, exitaction);
			Do(entryaction, entity.PostfixParameters, exitaction);
			exitaction(entity);
		}

		//
		// Traverse a chained entity invocation
		//
		template <typename EntryActionT, typename ExitActionT>
		void Do(EntryActionT& entryaction, AST::ChainedEntity& entity, ExitActionT& exitaction)
		{
			entryaction(entity);
			Do(entryaction, entity.Parameters, exitaction);
			Do(entryaction, entity.Code, exitaction);
			exitaction(entity);
		}

		//
		// Traverse a higher-order function parameter
		//
		template <typename EntryActionT, typename ExitActionT>
		void Do(EntryActionT& entryaction, AST::FunctionReferenceSignature& signature, ExitActionT& exitaction)
		{
			entryaction(signature);

			Markers::FunctionSignatureParams parammarker;
			entryaction(parammarker);
			Do(entryaction, signature.ParamTypes, exitaction);
			exitaction(parammarker);

			Markers::FunctionSignatureReturn retmarker;
			entryaction(retmarker);
			Do(entryaction, signature.ReturnType, exitaction);
			exitaction(retmarker);

			exitaction(signature);
		}

		//
		// Traverse a named function parameter
		//
		template <typename EntryActionT, typename ExitActionT>
		void Do(EntryActionT& entryaction, AST::NamedFunctionParameter& param, ExitActionT& exitaction)
		{
			entryaction(param);
			
			Markers::TemplateArgs marker;
			entryaction(marker);
			Do(entryaction, param.TemplateArgs, exitaction);
			exitaction(marker);

			Do(entryaction, param.IsReference, exitaction);
			exitaction(param);
		}

		//
		// Traverse a function parameter
		//
		template <typename EntryActionT, typename ExitActionT>
		void Do(EntryActionT& entryaction, AST::FunctionParameter& param, ExitActionT& exitaction)
		{
			entryaction(param);
			Do(entryaction, param.V, exitaction);
			exitaction(param);
		}

		//
		// Traverse a function tag
		//
		template <typename EntryActionT, typename ExitActionT>
		void Do(EntryActionT& entryaction, AST::FunctionTag& tag, ExitActionT& exitaction)
		{
			entryaction(tag);
			Do(entryaction, tag.TagName, exitaction);
			Do(entryaction, tag.Parameters, exitaction);
			exitaction(tag);
		}

		//
		// Traverse a function definition
		//
		template <typename EntryActionT, typename ExitActionT>
		void Do(EntryActionT& entryaction, AST::Function& function, ExitActionT& exitaction)
		{
			entryaction(function);
			Do(entryaction, function.Name, exitaction);
			Do(entryaction, function.TemplateParams, exitaction);
		
			Do(entryaction, function.Parameters, exitaction);
            
			{
				Markers::FunctionReturnExpression marker;
				entryaction(marker);
				Do(entryaction, function.Return, exitaction);
				exitaction(marker);
			}

			Do(entryaction, function.Tags, exitaction);
			Do(entryaction, function.Code, exitaction);
			exitaction(function);
		}

		//
		// Traverse a structure member definition (member variable case)
		//
		template <typename EntryActionT, typename ExitActionT>
		void Do(EntryActionT& entryaction, AST::StructureMemberVariable& variable, ExitActionT& exitaction)
		{
			entryaction(variable);

			Do(entryaction, variable.IsReference, exitaction);

			Markers::TemplateArgs marker;
			entryaction(marker);
			Do(entryaction, variable.TemplateArgs, exitaction);
			exitaction(marker);

			exitaction(variable);
		}

		//
		// Traverse a structure member which is a function reference
		//
		template <typename EntryActionT, typename ExitActionT>
		void Do(EntryActionT& entryaction, AST::StructureMemberFunctionRef& signature, ExitActionT& exitaction)
		{
			entryaction(signature);

			Markers::StructureFunctionParams parammarker;
			entryaction(parammarker);
			Do(entryaction, signature.ParamTypes, exitaction);
			exitaction(parammarker);

			Markers::StructureFunctionReturn retmarker;
			entryaction(retmarker);
			Do(entryaction, signature.ReturnType, exitaction);
			exitaction(retmarker);

			exitaction(signature);
		}

		//
		// Traverse a structure definition
		//
		template <typename EntryActionT, typename ExitActionT>
		void Do(EntryActionT& entryaction, AST::Structure& structure, ExitActionT& exitaction)
		{
			entryaction(structure);
			Do(entryaction, structure.TemplateParams, exitaction);
			Do(entryaction, structure.Members, exitaction);
			exitaction(structure);
		}

		//
		// Traverse a complete program from the AST root node downwards
		//
		template <typename EntryActionT, typename ExitActionT>
		void Do(EntryActionT& entryaction, AST::Program& program, ExitActionT& exitaction)
		{
			entryaction(program);
			Do(entryaction, program.MetaEntities, exitaction);
			exitaction(program);
		}

	private:

		//
		// General case: perform traversal actions for a leaf node
		//
        template<class NodeT, bool IsVariant>
        struct DoerDispatcher
        {
            template<typename EntryActionT, typename ExitActionT>
            static void Do(Traverser*, EntryActionT& entryaction, NodeT& node, ExitActionT& exitaction) 
            {
                entryaction(node);
                exitaction(node);
            }
        };

		//
		// Special case: unwrap a variant and traverse its contents
		//
        template<class NodeT>
        struct DoerDispatcher<NodeT, true>
        {
            template<typename EntryActionT, typename ExitActionT>
            static void Do(Traverser* t, EntryActionT& entryaction, NodeT& node, ExitActionT& exitaction) 
            {
			    VariantVisitor<EntryActionT, ExitActionT> visitor(*t, entryaction, exitaction);
			    boost::apply_visitor(visitor, node);			
            }
        };


		//
		// Helper visitor for unwrapping boost::variants
		//
		// Simply re-invokes the traverser with the original typed contents
		// of a variant. Invocation is templated so that any type contained
		// within the variant will be passed back to the traverser cleanly.
		//
		template <typename EntryActionT, typename ExitActionT>
		struct VariantVisitor : public boost::static_visitor<>
		{
			VariantVisitor(Traverser& traverser, EntryActionT& entry, ExitActionT& exit)
				: self(traverser),
				  Entry(entry),
				  Exit(exit)
			{ }

			template <typename T>
			void operator () (T& value)
			{
				self.Do(Entry, value, Exit);
			}

		// Non-copyable
		private:
			VariantVisitor(const VariantVisitor& rhs);
			VariantVisitor& operator = (const VariantVisitor& rhs);

		private:
			Traverser& self;
			EntryActionT& Entry;
			ExitActionT& Exit;
		};
	};


	//
	// Simple wrapper function for encapsulating traversal operations
	//
	template <typename TraverserT>
	void DoTraversal(TraverserT& tr, AST::Program& program)
	{
		ASTTraverse::Traverser traverse;
		traverse.Do(tr.Entry, program, tr.Exit);
	}

}

